/**
 * 279.完全平方数
 */
public class Exerciser8 {
    /**
     * 滚动数组优化
     * @param n
     * @return
     */
    public int numSquares(int n) {
        // 滚动数组优化
        int m = (int)Math.sqrt(n);
        int INF = 0x3f3f3f3f;
        // dp[i][j]: 从前i个数中挑选，对应的完全平方数的和正好等于j，
        int[] dp = new int[n + 1];
        // 初始化：
        for(int j = 1;j <= n;j++) {
            dp[j] = INF;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = i*i;j <= n;j++) {
                dp[j] = Math.min(dp[j],dp[j - i*i] + 1);
            }
        }
        return dp[n];
    }

    public int numSquares1(int n) {
        int m = (int)Math.sqrt(n);
        int INF = 0x3f3f3f3f;
        // dp[i][j]: 从前i个数中挑选，对应的完全平方数的和正好等于j，
        int[][] dp = new int[m + 1][n + 1];
        // 初始化：
        for(int j = 1;j <= n;j++) {
            dp[0][j] = INF;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = 0;j <= n;j++) {
                dp[i][j] = dp[i - 1][j];
                if(j >= i*i) {
                    dp[i][j] = Math.min(dp[i][j],dp[i][j - i*i] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
